package leetcode;

import java.util.Arrays;

public class Q0122 {
    /**
     * dp O(n^2) O(n)
     **/
//    public int maxProfit(int[] prices) {
//        int[] f = new int[prices.length + 1];
//        int res = 0;
//        for (int i = 0; i < prices.length; i++) {
//            for (int j = 0; j < i; j++) {
//                f[i + 1] = Math.max(f[j + 1], f[j + 1] + prices[i] - prices[j]);
//            }
//            res = Math.max(res, f[i + 1]);
//        }
//        return res;
//    }

    /**
     * dp O(n) O(n)
     **/
//    public int maxProfit(int[] prices) {
//        int[][] dp = new int[prices.length][2];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        for (int i = 1; i < prices.length; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//        }
//        return dp[prices.length - 1][0];
//    }

    /**
     * dp O(n) O(1)
     **/
    public int maxProfit(int[] prices) {
        int dp0 = 0;
        int dp1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int dp0New = Math.max(dp0, dp1 + prices[i]);
            int dp1New = Math.max(dp1, dp0 - prices[i]);
            dp0 = dp0New;
            dp1 = dp1New;
        }
        return dp0;
    }

    /**
     * 贪心 O(n) O(1)
     **/
//    public int maxProfit(int[] prices) {
//        int res = 0;
//        for (int i = 1; i < prices.length; i++) {
//            res += Math.max(0, prices[i] - prices[i - 1]);
//        }
//        return res;
//    }
    public static void main(String[] args) {
        Q0122 sl = new Q0122();
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(sl.maxProfit(prices));
    }
}
